#include "hw5.h"

/*****核心功能函数*****/
btree remove_node(btree target, btree root, bool right)
{
    /***待删结点或者根节点为空***/
    if (target == nullptr || root == nullptr)
    {
        return root;
    }
    /***待删结点或者根节点为空***/

    /***找到待删结点的父节点***/
    btree f = findF(target->data, root);
    /***找到待删结点的父节点***/

    /***待删结点的左孩子结点为空***/
    if (target->lc == nullptr)
    {
        /**待删结点就是根节点**/
        if (target == root)
        {
            root = target->rc;
            target = nullptr;
        }
        /**待删结点就是根节点**/

        /**待删结点不是根节点**/
        else
        {
            if (target == f->lc)
            {
                f->lc = target->rc;
            }
            if (target == f->rc)
            {
                f->rc = target->rc;
            }
        }
        /**待删结点不是根节点**/
        return root;
    }
    /***待删结点的左孩子结点为空***/

    /***待删结点的右孩子结点为空***/
    if (target->rc == nullptr)
    {
        /**待删结点就是根节点**/
        if (target == root)
        {
            root = target->lc;
            target = nullptr;
        }
        /**待删结点就是根节点**/

        /**待删结点不是根节点**/
        else
        {
            if (target == f->lc)
            {
                f->lc = target->lc;
            }
            if (target == f->rc)
            {
                f->rc = target->lc;
            }
        }
        /**待删结点不是根节点**/
        return root;
    }
    /***待删结点的右孩子结点为空***/

    /***待删结点的左右孩子结点均非空（取右子树最小值版本）***/
    if (right == true)
    {
        btree temp = target->rc;
        while (temp->lc != nullptr)
        {
            temp = temp->lc;
        }
        f = findF(temp->data, root);
        target->data = temp->data;
        if (f->lc == temp)
        {
            f->lc = nullptr;
        }
        if (f->rc == temp)
        {
            f->rc = nullptr;
        }
    }
    /***待删结点的左右孩子结点均非空（取右子树最小值版本）***/

    /***待删结点的左右孩子结点均非空（取左子树最大值版本）***/
    else
    {
        btree temp = target->lc;
        while (temp->rc != nullptr)
        {
            temp = temp->rc;
        }
        f = findF(temp->data, root);
        target->data = temp->data;
        if (f->lc == temp)
        {
            f->lc = nullptr;
        }
        if (f->rc == temp)
        {
            f->rc = nullptr;
        }
    }
    /***待删结点的左右孩子结点均非空（取左子树最大值版本）***/
    return root;
}
/*****核心功能函数*****/

int main()
{
    t0 = NULL;
    t1 = (btree)malloc(sizeof(btnode));
    t2 = (btree)malloc(sizeof(btnode));
    t3 = (btree)malloc(sizeof(btnode));
    t4 = (btree)malloc(sizeof(btnode));
    t5 = (btree)malloc(sizeof(btnode));
    t6 = (btree)malloc(sizeof(btnode));
    t7 = (btree)malloc(sizeof(btnode));
    t8 = (btree)malloc(sizeof(btnode));
    t9 = (btree)malloc(sizeof(btnode));

    /***空二叉树***/
    printf("*****空二叉树*****\n");
    t_init();
    print_t(t0);
    if (isBST(t0))
    {
        printf("\n待删除结点：%d\n", t1->data);
        printf("\n取右子树的最小值结点：\n");
        print_t(remove_node(t1, t0, true));
        printf("\n取左子树的最大值结点：\n");
        print_t(remove_node(t1, t0, false));
    }
    else
    {
        printf("不是二叉搜索树！\n");
    }
    v.clear();
    printf("*****空二叉树*****\n\n\n\n");
    /***空二叉树***/

    /***第1棵非空二叉树***/
    printf("/*****第1棵非空二叉树*****/\n");
    t_init();
    t1->lc = t2;
    t1->rc = t3;
    t2->lc = t4;
    t2->rc = t5;
    t3->lc = t6;
    t3->rc = t7;
    print_t(t1);
    if (isBST(t1))
    {
        printf("\n待删除结点：%d\n", t3->data);
        printf("\n取右子树的最小值结点：\n");
        print_t(remove_node(t3, t1, true));
        t_init();
        t1->lc = t2;
        t1->rc = t3;
        t2->lc = t4;
        t2->rc = t5;
        t3->lc = t6;
        t3->rc = t7;
        printf("\n取左子树的最大值结点：\n");
        print_t(remove_node(t3, t1, false));
    }
    else
    {
        printf("\n不是二叉搜索树！\n");
    }
    v.clear();
    printf("/*****第1棵非空二叉树*****/\n\n\n\n");
    /***第1棵非空二叉树***/

    /***第2棵非空二叉树***/
    printf("/*****第2棵非空二叉树*****/\n");
    t_init();
    t5->lc = t3;
    t3->lc = t2;
    t5->rc = t7;
    t7->lc = t6;
    t7->rc = t9;
    t9->lc = t8;
    print_t(t5);
    if (isBST(t5))
    {
        printf("\n待删除结点：%d\n", t7->data);
        printf("\n取右子树的最小值结点：\n");
        print_t(remove_node(t7, t5, true));
        t_init();
        t5->lc = t3;
        t3->lc = t2;
        t5->rc = t7;
        t7->lc = t6;
        t7->rc = t9;
        t9->lc = t8;
        printf("\n取左子树的最大值结点：\n");
        print_t(remove_node(t7, t5, false));
    }
    else
    {
        printf("\n不是二叉搜索树！\n");
    }
    v.clear();
    printf("/*****第2棵非空二叉树*****/\n\n\n\n");
    /***第2棵非空二叉树***/

    /***第3棵非空二叉树***/
    printf("/*****第3棵非空二叉树*****/\n");
    t_init();
    t5->lc = t3;
    t3->lc = t2;
    t3->rc = t4;
    t2->lc = t1;
    t5->rc = t7;
    t7->lc = t6;
    t7->rc = t9;
    t9->lc = t8;
    print_t(t5);
    if (isBST(t5))
    {
        printf("\n待删除结点：%d\n", t5->data);
        printf("\n取右子树的最小值结点：\n");
        print_t(remove_node(t5, t5, true));
        t_init();
        t5->lc = t3;
        t3->lc = t2;
        t3->rc = t4;
        t2->lc = t1;
        t5->rc = t7;
        t7->lc = t6;
        t7->rc = t9;
        t9->lc = t8;
        printf("\n取左子树的最大值结点：\n");
        print_t(remove_node(t5, t5, false));
    }
    else
    {
        printf("\n不是二叉搜索树！\n");
    }
    v.clear();
    printf("/*****第3棵非空二叉树*****/\n\n\n\n");
    /***第3棵非空二叉树***/

    /***第4棵非空二叉树***/
    printf("/*****第4棵非空二叉树*****/\n");
    t_init();
    t5->lc = t3;
    t3->lc = t2;
    t3->rc = t4;
    t2->lc = t1;
    t5->rc = t7;
    t7->lc = t6;
    t7->rc = t9;
    t9->lc = t8;
    print_t(t5);
    if (isBST(t5))
    {
        printf("\n待删除结点：%d\n", t6->data);
        printf("\n取右子树的最小值结点：\n");
        print_t(remove_node(t6, t5, true));
        t_init();
        t5->lc = t3;
        t3->lc = t2;
        t3->rc = t4;
        t2->lc = t1;
        t5->rc = t7;
        t7->lc = t6;
        t7->rc = t9;
        t9->lc = t8;
        printf("\n取左子树的最大值结点：\n");
        print_t(remove_node(t6, t5, false));
    }
    else
    {
        printf("\n不是二叉搜索树！\n");
    }
    v.clear();
    printf("/*****第4棵非空二叉树*****/\n\n\n\n");
    /***第4棵非空二叉树***/

    system("pause");
}